package com.zyk.leetcode;

import java.util.HashSet;

/**
 * @author zhangsan
 * @date 2021/4/8 10:36
 */
public class M0207 {

    // https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 两个链表如果相交, 让两个指针都走一遍headA + headB, 相等的节点既是相交的节点
        ListNode a=headA, b=headB;
        while (a != b) {
            a = a==null? headB : a.next;
            b = b==null? headA : b.next;
        }
        return a;
    }

    // 暴力解HashSet
    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        // 两个链表如果相交, 让两个指针都走一遍headA + headB, 相等的节点既是相交的节点
        HashSet<ListNode> set = new HashSet<>();
        ListNode cur = headA;
        while (cur != null) {
            set.add(cur);
            cur = cur.next;
        }
        cur = headB;
        while (cur != null) {
            if(set.contains(cur)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }


}
